package com.xxd.algo.leetcode.topinterviewquestions;

public class Problem_0204_CountPrimes {

    public static int countPrimes(int n) {
        if (n < 3) {
            return 0;
        }
        // fi true 代表不是质数
		// fi false 代表是i是质数
        boolean[] f = new boolean[n];
        int count = n / 2;
        for (int i = 3; i * i < n; i += 2) {
            if (f[i]) {
                continue;
            }
            for (int j = i * i; j < n; j += 2 * i) { // J 画×的位置
                if (!f[j]) {
                    --count;
                    f[j] = true;
                }
            }
        }
        return count;
    }

}
